17. 图的遍历

题目内容

给定一个无向图，顶点编号从 1 到 n；从顶点 1 出发，进行深度优先搜索（DFS），当某个顶点有多个邻接点时，按照编号从小到大的顺序依次访问，输出遍历过程中访问顶点的顺序。1 ≤ n ≤ 100，0 ≤ m ≤ 100。若不连通，DFS 从顶点 1 出发无法遍历所有顶点，输出只包含可达顶点。输入保证没有自环如 (i,i)，即顶点到自身的边；同时输入保证不会有多条相同的边，如 (1,2) 出现两次。

输入描述

• 整数 n, m：表示顶点数和边数；
• 二维数组 graph：每个元素有两个整数 u, v，表示 u 和 v 之间有一条无向边。

输出描述

数组：数组元素表示深度优先搜索访问顶点的顺序（从 1 开始）。

样例

样例 1

输入

6 5
1 2
1 3
2 4
3 5
3 6

输出

1,2,4,3,5,6

说明：

• 从 1 出发，邻接点有 {2,3}，选小的 2
• 从 2 出发，邻接点有 {1,4}，1 已访问，选 4
• 4 没有未访问邻接点，回溯到 2，回溯到 1，下一个未访问的是 3
• 从 3 出发，邻接点有 {1,5,6}，1 已访问，选小的 5
• 5 没有未访问邻接点，回溯到 3，下一个未访问的是 6
• 6 结束，遍历完成。最终访问顺序为 [1,2,4,3,5,6]。

样例 2

输入

5 2
1 2
3 4

输出

1,2

说明：

• 从 1 出发，邻接点有 {2}，选 2
• 从 2 出发，邻接点有 {1}，1 已访问，没有未访问邻接点，回溯到 1
• 1 没有其他未访问邻接点，遍历结束。顶点 3、4、5 与 1 不连通，无法到达，因此不输出。最终访问顺序为 [1,2]。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];
rl.on('line', (input) => {
    lines.push(input.split(' ').map(Number));
})
rl.on('close', () => {
    const [n, m] = lines.shift();
    const graph = lines;
    const map = Array.from({ length: n + 1 }, () => []);
    const used = Array(n+1).fill(false);
    const ans = [];
    for(let i=0; i<graph.length; i++) {
        const [x, y] = graph[i];
        map[x].push(y);
        map[y].push(x);
    }
    for(let x in map) {
        map[x] = map[x].sort((a,b) => a-b);
    }
    const dfs = (n) => {
        ans.push(n);
        used[n] = true;
        for(let i=0; i<map[n].length; i++) {
            if(!used[map[n][i]]) {
                dfs(map[n][i]);
            }
        }
    }
    dfs(1);
    console.log(ans.join(','));
})